package com.buddy.learn.algorithm.simple;

import java.util.Arrays;

/**
 * 归并排序 平均时间复杂度均为 O(nlogn)
 * 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法
 * 该算法采用经典的分治（divide-and-conquer）策略
 * 分治法将问题:
 *  分(divide)成一些小的问题然后递归求解
 *  治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起
 *  即分而治之。
 * @author Buddy
 * @date 2021/4/21
 */
public class Sort_Merge {

    public static void main(String[] args) {
        int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
        System.out.println("排序前:  " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("排序后:  " + Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        // 计算中间值，这种算法保证不会溢出
        int mid = low + ((high - low) >> 1);
        // 先对左边排序
        mergeSort(arr, low, mid);
        // 先对右边排序
        mergeSort(arr, mid + 1, high);
        // 归并两个有序的子序列
        merge(arr,low,mid,high);
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        // temp[]是临时数组，包左不包右，所以要额外 + 1。
        int[] temp = new int[high - low + 1];
        // 左侧指针从low开始
        int left = low;
        // 右侧指针从mid+1开始
        int right = mid + 1;
        // 此索引用于temp[]
        int index = 0;
        // 当两个子序列还有元素时，从小到大放入temp[]中。
        while (left <= mid && right <= high) {
            if (arr[left] < arr[right]) {
                temp[index++] = arr[left++];
            } else {
                temp[index++] = arr[right++];
            }
        }

        // 要么左边没有元素
        while (left <= mid) {
            temp[index++] = arr[left++];
        }

        // 要么右边没有元素
        while (right <= high) {
            temp[index++] = arr[right++];
        }

        // 重新赋值给arr对应的区间。
        for (int i = 0; i < temp.length; i++) {
            arr[low + i] = temp[i];
        }
    }
}
